package com.xiaoyg.algorithm;

import java.util.Arrays;

public class MergeSortArray {

    public static void main(String[] args) {
        int []nums1 = {1,5,6,0,0,0};
        int []nums2 = {2,4,7};
        merge2(nums1, 3, nums2, 3);
        for (int i : nums1) {
            System.out.print(i);
        }
    }

    //使用java api实现排序
    public static void merge(int []nums1,int m, int []nums2,int n){
        for (int i = 0; i < n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }

    public static void merge1(int []nums1,int m, int []nums2,int n){
        int k = m + n;
        int [] temp = new int [k];
        int index = 0;
        int nums1Index=0;
        int nums2Index=0;
        while(index < k){
            //nums1 读完
            if (nums1Index >= m){
                temp[index] = nums2[nums2Index];
                index++;
                nums2Index++;
                continue;
            }
            //nums2 读完
            if (nums2Index >= n){
                temp[index] = nums1[nums1Index];
                index ++;
                nums1Index++;
                continue;
            }

            if (nums1[nums1Index] <= nums2[nums2Index]){
                temp[index] = nums1[nums1Index];
                index ++;
                nums1Index++;
            } else {
                temp[index] = nums2[nums2Index];
                index++;
                nums2Index++;
            }
        }
        for (int i = 0; i < temp.length; i++) {
            nums1[i] = temp[i];
        }
    }


    public static void merge2(int []nums1,int m, int []nums2,int n){
        //不使用数组
        int k = m + n;
        int nums1Index = m - 1;
        int nums2index = n - 1;
        int index = k - 1;
        while (index >= 0){
            if (nums1Index < 0){
                nums1[index] = nums2[nums2index];
                index--;
                nums2index--;
                continue;
            }
            if (nums2index < 0){
                nums1[index] = nums1[nums1Index];
                index--;
                nums1Index--;
                continue;
            }
            if (nums2[nums2index] >= nums1[nums1Index]){
                nums1[index] = nums2[nums2index];
                index--;
                nums2index--;
            }else {
                nums1[index] = nums1[nums1Index];
                index--;
                nums1Index--;
            }
        }
    }
}
